#include <stdio.h>
#include <malloc.h>


/**
 * Definition for a binary tree node.  */
 struct TreeNode {
     int val;
     struct TreeNode *left;
     struct TreeNode *right;
 };



#define MAX_STR_LEN 100000

void helper(struct TreeNode* root, char * str, int * pos) { // 再理解？？？
    if (root == NULL) {
        return;
    }
    if (root->left == NULL && root->right == NULL) {
        *pos += sprintf(str + *pos, "%d", root->val);
        return;
    }
    if (root->right == NULL) {
        *pos += sprintf(str + *pos, "%d", root->val);
        str[(*pos)++] = '(';
        helper(root->left, str, pos);
        str[(*pos)++] = ')';
    } else {
        *pos += sprintf(str + *pos, "%d", root->val);
        str[(*pos)++] = '(';
        helper(root->left, str, pos);
        str[(*pos)++] = ')';
        str[(*pos)++] = '(';
        helper(root->right, str, pos);
        str[(*pos)++] = ')';
    }
}

// 方法一：递归
char * tree2str_1(struct TreeNode* root) {
    char * res = (char *)malloc(sizeof(char) * MAX_STR_LEN);
    int pos = 0;
    helper(root, res, &pos);
    res[pos] = '\0';
    return res;
}



#include ".\lib\uthash-master\src\uthash.h" /* UT_hash_handle */

// 方法二：迭代
#define MAX_STR_LEN 100000
#define MAX_NODE_SIZE 100000

typedef struct {
    struct TreeNode * key;
    UT_hash_handle hh;
} HashItem;

char * tree2str(struct TreeNode* root){
    char * ans = (char *)malloc(sizeof(char) * MAX_STR_LEN);
    int pos = 0;
    struct TreeNode ** st = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * MAX_NODE_SIZE);
    HashItem * vis = NULL;
    int top = 0;
    st[top++] = root;

    while (top > 0) {
        struct TreeNode * node = st[top - 1];
        HashItem * pEntry = NULL;
        HASH_FIND_PTR(vis, &node, pEntry);
        if (pEntry != NULL) {
            if (node != root) {
                ans[pos++] = ')';
            }
            top--;
        } else {
            pEntry = (HashItem *)malloc(sizeof(HashItem));
            pEntry->key = node;
            HASH_ADD_PTR(vis, key, pEntry);
            if (node != root) {
                ans[pos++] = '(';
            }
            pos += sprintf(ans + pos, "%d", node->val);
            if (node->left == NULL && node->right != NULL) {
                pos += sprintf(ans + pos, "()");
            }
            if (node->right != NULL) {
                st[top++] = node->right;
            }
            if (node->left != NULL) {
                st[top++] = node->left;
            }
        }
    }
    ans[pos] = '\0';
    free(st);
    HashItem * curr, * next;
    HASH_ITER(hh, vis, curr, next) {
        HASH_DEL(vis, curr);
        free(curr);
    }
    return ans;
}


int main() {
    // 1、c语言不知道怎么输入；
    // 2、怎么把字符转为二叉树？？
}